<!DOCTYPE html>
<html>
<head>
<script>
(function(){
    var bp = document.createElement('script');
    var curProtocol = window.location.protocol.split(':')[0];
    if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
    }
    else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
    }
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(bp, s);
})();
</script>
<script>
var _hmt = _hmt || [];
(function() {
  var hm = document.createElement("script");
  hm.src = "https://hm.baidu.com/hm.js?d890b1f16fb364253e79c5bb20225c3a";
  var s = document.getElementsByTagName("script")[0]; 
  s.parentNode.insertBefore(hm, s);
})();
</script>


    

    

    
<!-- Baidu Tongji -->
<script>var _hmt = _hmt || []</script>
<script async src="//hm.baidu.com/hm.js?busuanzi_value_site_uv"></script>
<!-- End Baidu Tongji -->




    <meta charset="utf-8">
    <meta name="baidu-site-verification" content="FYMCShbUK8" />
    <meta name="baidu-site-verification" content="ZYRF7OxQRW" />
    <meta name="baidu-site-verification" content="cHSqtjI0PN" />
    <meta name="baidu-site-verification" content="cHSqtjI0PN" />
    <meta name="baidu-site-verification" content="cHSqtjI0PN" />
    
    
    <link rel="canonical" href="https://hhardyy.com/2018/12/20/数据结构与算法之美手记/">
    
    
    <title>数据结构与算法之美手记 | 小方块 - hhardyy.com | 复杂的坑+归其原理+了解实现规则===解决？解决成功：加油解决成功;</title>
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    
    <meta name="theme-color" content="#958e93">
    
    
    <meta name="keywords" content="算法">
    <meta name="description" content="跟随Google大佬的脚步。。。（一如既往的跟不上）">
<meta name="keywords" content="算法">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构与算法之美手记">
<meta property="og:url" content="http://yoursite.com/2018/12/20/数据结构与算法之美手记/index.html">
<meta property="og:site_name" content="小方块 - hhardyy.com">
<meta property="og:description" content="跟随Google大佬的脚步。。。（一如既往的跟不上）">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="http://yoursite.com/images/Algorithm/4.jpg">
<meta property="og:image" content="http://yoursite.com/images/Algorithm/5.jpg">
<meta property="og:image" content="http://yoursite.com/images/Algorithm/1.JPG">
<meta property="og:image" content="http://yoursite.com/images/Algorithm/2.JPG">
<meta property="og:image" content="http://yoursite.com/images/Algorithm/3.JPG">
<meta property="og:updated_time" content="2020-01-13T15:37:33.065Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="数据结构与算法之美手记">
<meta name="twitter:description" content="跟随Google大佬的脚步。。。（一如既往的跟不上）">
<meta name="twitter:image" content="http://yoursite.com/images/Algorithm/4.jpg">
    
        <link rel="alternate" type="application/atom+xml" title="小方块 - hhardyy.com" href="/atom.xml">
    
    <link rel="shortcut icon" href="/hardyfavicon.ico">
    <link rel="stylesheet" href="//unpkg.com/hexo-theme-material-indigo@latest/css/style.css">
    <script>window.lazyScripts=[]</script>

    <!-- custom head -->
    

</head>

<body>
    <div id="loading" class="active"></div>

    <aside id="menu" class="hide" >
  <div class="inner flex-row-vertical">
    <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menu-off">
        <i class="icon icon-lg icon-close"></i>
    </a>
    <div class="brand-wrap" style="background-image:url(/img/paulGraham.jpg)">
      <div class="brand" style="background-color:#4154b2">
        <a href="/" class="avatar waves-effect waves-circle waves-light">
          <img src="/img/avatar.jpg">
        </a>
        <hgroup class="introduce">
          <h5 class="nickname">BingZhenhuang</h5>
          <a href="mailto:huangbingzhen@hhardyy.com" title="huangbingzhen@hhardyy.com" class="mail">huangbingzhen@hhardyy.com</a>
        </hgroup>
      </div>
    </div>
    <div class="scroll-wrap flex-col">
      <ul class="nav">
        
            <li class="waves-block waves-effect">
              <a href="/"  >
                <i class="icon icon-lg icon-home"></i>
                主页
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/archives"  >
                <i class="icon icon-lg icon-archives"></i>
                所有文章
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/tags"  >
                <i class="icon icon-lg icon-tags"></i>
                标签
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://github.com/HHardyy" target="_blank" >
                <i class="icon icon-lg icon-github"></i>
                Github
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://juejin.im/user/59a26f926fb9a02487553b04"  >
                <i class="icon icon-lg icon-pencil"></i>
                掘金-圳
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://segmentfault.com/u/hhardyy"  >
                <i class="icon icon-lg icon-comments"></i>
                Segmentfault
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://codepen.io/HHardyy/" target="_blank" >
                <i class="icon icon-lg icon-codepen"></i>
                Codepen
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/ZhenSolive/find.html" target="_blank" >
                <i class="icon icon-lg icon-globe"></i>
                原生直播间
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/hero/judge.html" target="_blank" >
                <i class="icon icon-lg icon-cloud"></i>
                原生小悟空
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/airPlay/HHardyy_PC.html" target="_blank" >
                <i class="icon icon-lg icon-camera"></i>
                原生飞机大战（PC）
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://www.freecodecamp.cn/hhardyy" target="_blank" >
                <i class="icon icon-lg icon-leaf"></i>
                Freecodecamp
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/友情链接"  >
                <i class="icon icon-lg icon-link"></i>
                友链
              </a>
            </li>
        
      </ul>
    </div>
  </div>
</aside>

    <main id="main">
        <header class="top-header" id="header">
    <div class="flex-row">
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light on" id="menu-toggle">
          <i class="icon icon-lg icon-navicon"></i>
        </a>
        <div class="flex-col header-title ellipsis">数据结构与算法之美手记</div>
        
        <div class="search-wrap" id="search-wrap">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="back">
                <i class="icon icon-lg icon-chevron-left"></i>
            </a>
            <input type="text" id="key" class="search-input" autocomplete="off" placeholder="输入感兴趣的关键字">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="search">
                <i class="icon icon-lg icon-search"></i>
            </a>
        </div>
        
        
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menuShare">
            <i class="icon icon-lg icon-share-alt"></i>
        </a>
        
    </div>
</header>
<header class="content-header post-header">

    <div class="container fade-scale">
        <h1 class="title">数据结构与算法之美手记</h1>
        <h5 class="subtitle">
            
                <time datetime="2018-12-20T01:25:03.000Z" itemprop="datePublished" class="page-time">
  2018-12-20
</time>


            
        </h5>
    </div>

    


</header>


<div class="container body-wrap">
    
    <aside class="post-widget">
        <nav class="post-toc-wrap" id="post-toc">
            <h4>TOC</h4>
            <ol class="post-toc"><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#什么是数据结构？什么是算法？"><span class="post-toc-number">1.</span> <span class="post-toc-text">什么是数据结构？什么是算法？</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#数据结构和算法有什么关系？"><span class="post-toc-number">2.</span> <span class="post-toc-text">数据结构和算法有什么关系？</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#我们怎么选用合适的数据结构和算法？有什么衡量标准吗？"><span class="post-toc-number">3.</span> <span class="post-toc-text">我们怎么选用合适的数据结构和算法？有什么衡量标准吗？</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#几种常见时间复杂度实例分析"><span class="post-toc-number">4.</span> <span class="post-toc-text">几种常见时间复杂度实例分析</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#多项式时间复杂度"><span class="post-toc-number">4.1.</span> <span class="post-toc-text">多项式时间复杂度</span></a></li></ol></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#十个经典的排序算法"><span class="post-toc-number">5.</span> <span class="post-toc-text">十个经典的排序算法</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#1、冒泡排序"><span class="post-toc-number">6.</span> <span class="post-toc-text">1、冒泡排序</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#2、-选择排序"><span class="post-toc-number">7.</span> <span class="post-toc-text">2、 选择排序</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#3、插入排序"><span class="post-toc-number">8.</span> <span class="post-toc-text">3、插入排序</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#4、希尔排序"><span class="post-toc-number">9.</span> <span class="post-toc-text">4、希尔排序</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#5、归并排序"><span class="post-toc-number">10.</span> <span class="post-toc-text">5、归并排序</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#6、快速排序"><span class="post-toc-number">11.</span> <span class="post-toc-text">6、快速排序</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#7、堆排序"><span class="post-toc-number">12.</span> <span class="post-toc-text">7、堆排序</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#8、计数排序"><span class="post-toc-number">13.</span> <span class="post-toc-text">8、计数排序</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#9、桶排序"><span class="post-toc-number">14.</span> <span class="post-toc-text">9、桶排序</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#10、基数排序"><span class="post-toc-number">15.</span> <span class="post-toc-text">10、基数排序</span></a></li></ol>
        </nav>
    </aside>
    
<article id="post-数据结构与算法之美手记"
  class="post-article article-type-post fade" itemprop="blogPost">

    <div class="post-card">
        <h1 class="post-card-title">数据结构与算法之美手记</h1>
        <div class="post-meta">
            <time class="post-time" title="2018-12-20 09:25:03" datetime="2018-12-20T01:25:03.000Z"  itemprop="datePublished">2018-12-20</time>

            


            

        </div>
        <div class="post-content" id="post-content" itemprop="postContent">
            <p>跟随Google大佬的脚步。。。（一如既往的跟不上）</p>
<p><iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width="330" height="86" src="//music.163.com/outchain/player?type=2&id=486412012&auto=0&height=66"></iframe><br><a id="more"></a></p>
<p>突然看到《数据结构与算法之美》，突然买，突然看，突然继续看，突然反复看。。。</p>
<h3 id="什么是数据结构？什么是算法？"><a href="#什么是数据结构？什么是算法？" class="headerlink" title="什么是数据结构？什么是算法？"></a>什么是数据结构？什么是算法？</h3><p>1、从广义上讲，数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。<br>举例：<br>图书馆储藏书籍你肯定见过吧？为了方便查找，图书管理员一般会将书籍分门别类进行“存储”。按照一定规律编号，就是书籍这种“数据”的存储结构。<br>那我们如何来查找一本书呢？有很多种办法，你当然可以一本一本地找，也可以先根据书籍类别的编号，是人文，还是科学、计算机，来定位书架，然后再依次查找。笼统地说，这些查找方法都<br>是算法。<br>2、从狭义上讲，是指某些著名的数据结构和算法，比如队列、栈、堆、二分查找、动态规划等。这些都是前人智慧的结晶，都是前人从很多实际操作场景中抽象出来的，经过非常多的求证和检验，<br>可以高效地帮助我们解决很多实际的开发问题。</p>
<h3 id="数据结构和算法有什么关系？"><a href="#数据结构和算法有什么关系？" class="headerlink" title="数据结构和算法有什么关系？"></a>数据结构和算法有什么关系？</h3><p>数据结构是为算法服务的，算法要作用在特定的数据结构之上。<br>举例：<br>数组具有随机访问的特点，常用的二分查找算法需要用数组来存储数据。但如果我们选择链表这种数据结构，二分查找算法就无法工作了，因为链表并不支持随机访问。<br>数据结构是静态的，它只是组织数据的一种方式。如果不在它的基础上操作、构建算法，孤立存在的数据结构就是没用的。</p>
<h3 id="我们怎么选用合适的数据结构和算法？有什么衡量标准吗？"><a href="#我们怎么选用合适的数据结构和算法？有什么衡量标准吗？" class="headerlink" title="我们怎么选用合适的数据结构和算法？有什么衡量标准吗？"></a>我们怎么选用合适的数据结构和算法？有什么衡量标准吗？</h3><p>衡量的标准(metric)—时间复杂度和空间复杂度，也就是数据结构与算法中最重要的概念——复杂度分析。数据结构和算法解决的是如何更省、更快地存储和处理数据的问题，因此，我们就需要<br>一个考量效率和资源消耗的方法，这就是复杂度分析方法，知道怎么去分析复杂度，才能得出正确的判断。</p>
<h3 id="几种常见时间复杂度实例分析"><a href="#几种常见时间复杂度实例分析" class="headerlink" title="几种常见时间复杂度实例分析"></a>几种常见时间复杂度实例分析</h3><p>虽然代码千差万别，但是常见的复杂度量级并不多。我稍微总结了一下，这些复杂度量级几乎涵盖了了你今后可以接触的所有代码的复杂度量级。<br><figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="/images/Algorithm/4.jpg" alt="复杂度量级，按数量级递增" title="">
                </div>
                <div class="image-caption">复杂度量级，按数量级递增</div>
            </figure><br>可以粗略地分为两类，多项式量级和非多项式量级，其中，非多项式量级只有两个：O(2n) 和 O(n!)。<br>当数据规模n越来越大时，非多项式量级的算法的执行时间会急剧增加，求解决问题的执行时间会无限增长，所以非多项式时间复杂度的算法其实是非常低效的算法。</p>
<h4 id="多项式时间复杂度"><a href="#多项式时间复杂度" class="headerlink" title="多项式时间复杂度"></a>多项式时间复杂度</h4><p>1、O（1）<br>O（1）只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码，比如这段代码，即便有三行，它的时间复杂度也是O（1），而不是O（3）。<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div></pre></td><td class="code"><pre><div class="line">int i = <span class="number">8</span>;</div><div class="line">int j = <span class="number">6</span>;</div><div class="line">int sum = i + j;</div></pre></td></tr></table></figure></p>
<p>总结：只要代码的执行时间不随着n的增大而增大，这样代码的时间复杂度我们都记作O（1）。或者说，一般情况下，只要算法中不存在循环语句，递归语句，即使有成千上万行的代码，其时间复杂度也是O（1）。</p>
<p>2、O（logn）、O（nlogn）<br>对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div></pre></td><td class="code"><pre><div class="line">i=<span class="number">1</span>;</div><div class="line"><span class="keyword">while</span> (i &lt;= n)  &#123;</div><div class="line">  i = i * <span class="number">2</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>
<p>根据复杂度分析方法，第三行代码是循环执行次数最多的，所以，只要能计算出这行代码被执行了多少次，就能知道整段代码的时间复杂度。<br>从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。还记得我们高中学过的等比数列吗？实际上，变量 i 的取值就是一个等比数列。<br>如果把它一个一个列出来，就应该是这个样子的：<br><figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="/images/Algorithm/5.jpg" alt="" title="">
                </div>
                <div class="image-caption"></div>
            </figure><br>所以，只要知道 x 值是多少,就知道这行代码执行的次数了。通过 2x=n 求解 x。所以，这段代码的时间复杂度就是 O(log2n)。<br>现在，把代码稍微改下，再看看，这段代码的时间复杂度是多少？<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div></pre></td><td class="code"><pre><div class="line">i=<span class="number">1</span>;</div><div class="line"><span class="keyword">while</span> (i &lt;= n)  &#123;</div><div class="line">  i = i * <span class="number">3</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>
<p>根据刚刚的思路，很简单就能看出来,这段代码的时间复杂度为 O(log3n)。实际上，不管是以 2 为底、以 3 为底，还是以 10 为底。我们可以把所有对数阶的时间复杂度都记<br>为 O(logn)。为什么呢？<br>我们知道，对数之间是可以互相转换的，log3n 就等于 log32 <em> log2n，所以 O(log3n) = O(C </em>log2n)，其中 C=log32 是一个常量。基于我们前面的一个理论：在采用大<br>O标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))。所以，O(log2n) 就等于 O(log3n)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。</p>
<h3 id="十个经典的排序算法"><a href="#十个经典的排序算法" class="headerlink" title="十个经典的排序算法"></a>十个经典的排序算法</h3><p>看java算法教程时候的截图笔记~~~~<br><figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="/images/Algorithm/1.JPG" alt="十大经典排序算法导图" title="">
                </div>
                <div class="image-caption">十大经典排序算法导图</div>
            </figure><br><figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="/images/Algorithm/2.JPG" alt="对比表中关键字字母解释" title="">
                </div>
                <div class="image-caption">对比表中关键字字母解释</div>
            </figure><br><figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="/images/Algorithm/3.JPG" alt="各种术语说明" title="">
                </div>
                <div class="image-caption">各种术语说明</div>
            </figure>  </p>
<h3 id="1、冒泡排序"><a href="#1、冒泡排序" class="headerlink" title="1、冒泡排序"></a>1、冒泡排序</h3><p>两两比较相邻的数字，左边比右边大就做交换<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">function</span> <span class="title">bubble</span>(<span class="params">arr,n</span>)</span>&#123;</div><div class="line">	<span class="keyword">let</span> temp=<span class="literal">null</span>;</div><div class="line">	<span class="keyword">for</span>(<span class="keyword">let</span> i=<span class="number">0</span>;i&lt;n<span class="number">-1</span>;i++)&#123;</div><div class="line">		<span class="keyword">if</span>(arr[i]&gt;arr[i+<span class="number">1</span>])&#123;</div><div class="line">			temp=arr[i];</div><div class="line">			arr[i]=arr[i+<span class="number">1</span>];</div><div class="line">			arr[i+<span class="number">1</span>]=temp;</div><div class="line">		&#125;</div><div class="line">	&#125;</div><div class="line">&#125;<span class="comment">//走一遍冒泡</span></div><div class="line"><span class="function"><span class="keyword">function</span> <span class="title">sortBble</span>(<span class="params">arr,n</span>)</span>&#123;</div><div class="line">	<span class="keyword">for</span>(<span class="keyword">let</span> i = n;i&gt;=<span class="number">1</span>;i--)&#123;</div><div class="line">		bubble(arr,i)</div><div class="line">	&#125;</div><div class="line">&#125;<span class="comment">//走一组冒泡</span></div><div class="line"><span class="keyword">let</span> arr=[<span class="number">1</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">7</span>,<span class="number">5</span>,<span class="number">6</span>,<span class="number">4</span>,<span class="number">9</span>,<span class="number">8</span>,<span class="number">0</span>]</div><div class="line">sortBble(arr,arr.length)</div><div class="line"><span class="built_in">console</span>.log(arr)</div></pre></td></tr></table></figure></p>
<p>有一个骚操作是可以提高冒泡排序的性能，降低时间复杂度的，也是刚get的新技能，那就是亦或，也就是这个东西^,举个栗子,封装一个冒泡排序，普通操作<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div></pre></td><td class="code"><pre><div class="line">function sortFunc(arr)&#123;</div><div class="line">	for(let i = 0; i &lt; arr.length; i++)&#123;</div><div class="line">	   for(let j = 0; j &lt;= arr.length - i - 1; j++)&#123;</div><div class="line">	       if(arr[j]&gt;arr[j+1])&#123;</div><div class="line">	           //普通操作</div><div class="line">    	       //let wap = arr[j];</div><div class="line">    	       //arr[j] = arr[j+1];</div><div class="line">    	       //arr[j+1] = wap;</div><div class="line">    </div><div class="line">    	       //亦或操作</div><div class="line">    	       arr[j] = arr[j]^arr[j+1];</div><div class="line">    	       arr[j+1] = arr[j]^arr[j+1];</div><div class="line">    	       arr[j] = arr[j]^arr[j+1];</div><div class="line">	       &#125;</div><div class="line">	   &#125;</div><div class="line">	&#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>
<h3 id="2、-选择排序"><a href="#2、-选择排序" class="headerlink" title="2、 选择排序"></a>2、 选择排序</h3><p>每次走一遍数组，找到最大的数字，然后和最后一个做交换<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">function</span> <span class="title">getMaxIndex</span>(<span class="params">arr,n</span>)</span>&#123;</div><div class="line">	<span class="keyword">let</span> max=arr[<span class="number">0</span>];</div><div class="line">	<span class="keyword">for</span>(<span class="keyword">let</span> i=<span class="number">0</span>;i&lt;n;i++)&#123;</div><div class="line">		<span class="keyword">if</span> (arr[i]&gt;max) &#123;</div><div class="line">			max=arr[i]</div><div class="line">		&#125;</div><div class="line">	&#125;</div><div class="line">	<span class="keyword">return</span> arr.indexOf(max)</div><div class="line">&#125;</div><div class="line"><span class="function"><span class="keyword">function</span> <span class="title">selectionSort</span>(<span class="params">arr,n</span>)</span>&#123;</div><div class="line">	<span class="keyword">let</span> maxIndex,temp;</div><div class="line">	<span class="keyword">for</span>(<span class="keyword">let</span> j=n;j&gt;<span class="number">0</span>;j--)&#123;</div><div class="line">		maxIndex=getMaxIndex(arr,j)</div><div class="line">		temp=arr[maxIndex];</div><div class="line">		arr[maxIndex]=arr[j<span class="number">-1</span>];</div><div class="line">		arr[j<span class="number">-1</span>]=temp;</div><div class="line">	&#125;</div><div class="line">	<span class="keyword">return</span> arr</div><div class="line">&#125;</div><div class="line"><span class="keyword">let</span> arr=[<span class="number">1</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">7</span>,<span class="number">5</span>,<span class="number">6</span>,<span class="number">4</span>,<span class="number">9</span>,<span class="number">8</span>,<span class="number">0</span>]</div><div class="line"><span class="built_in">console</span>.log(selectionSort(arr,arr.length))</div></pre></td></tr></table></figure></p>
<h3 id="3、插入排序"><a href="#3、插入排序" class="headerlink" title="3、插入排序"></a>3、插入排序</h3><p>将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">function</span> <span class="title">insert</span>(<span class="params">arr,n</span>)</span>&#123;</div><div class="line">	<span class="keyword">let</span> key=arr[n]</div><div class="line">	<span class="keyword">let</span> i=n</div><div class="line">	<span class="keyword">for</span>(i;arr[i<span class="number">-1</span>]&gt;key;i--)&#123;</div><div class="line">		<span class="keyword">if</span>(i&lt;=<span class="number">0</span>)&#123;</div><div class="line">			<span class="keyword">return</span></div><div class="line">		&#125;</div><div class="line">		arr[i]=arr[i<span class="number">-1</span>];</div><div class="line">	&#125;</div><div class="line">	<span class="keyword">return</span> arr[i]=key;</div><div class="line">&#125;</div><div class="line"><span class="function"><span class="keyword">function</span> <span class="title">insertSort</span>(<span class="params">arr,n</span>)</span>&#123;</div><div class="line">	<span class="keyword">for</span>(<span class="keyword">let</span> i=<span class="number">0</span>;i&lt;n;i++)&#123;</div><div class="line">		insert(arr,i)</div><div class="line">	&#125;</div><div class="line">	<span class="keyword">return</span> arr</div><div class="line">&#125;</div><div class="line"><span class="keyword">let</span> arr=[<span class="number">1</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">7</span>,<span class="number">5</span>,<span class="number">6</span>,<span class="number">4</span>,<span class="number">9</span>,<span class="number">8</span>,<span class="number">0</span>]</div><div class="line"><span class="built_in">console</span>.log(insertSort(arr,arr.length))</div></pre></td></tr></table></figure></p>
<h3 id="4、希尔排序"><a href="#4、希尔排序" class="headerlink" title="4、希尔排序"></a>4、希尔排序</h3><p>插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">function</span> <span class="title">shellSort</span>(<span class="params">arr</span>) </span>&#123;</div><div class="line">　　<span class="keyword">var</span> len = arr.length,</div><div class="line">　　temp,</div><div class="line">　　gap = <span class="number">1</span>;</div><div class="line">　　<span class="keyword">while</span>(gap &lt; len/<span class="number">5</span>) &#123; </div><div class="line">　　　　gap =gap*<span class="number">5</span>+<span class="number">1</span>;</div><div class="line">　　&#125;</div><div class="line">　　<span class="keyword">for</span> (gap; gap &gt; <span class="number">0</span>; gap = <span class="built_in">Math</span>.floor(gap/<span class="number">5</span>)) &#123;</div><div class="line">　　　　<span class="keyword">for</span> (<span class="keyword">var</span> i = gap; i &lt; len; i++) &#123;</div><div class="line">　　　　　　temp = arr[i];</div><div class="line">　　　　　　<span class="keyword">for</span> (<span class="keyword">var</span> j = i-gap; j &gt;= <span class="number">0</span> &amp;&amp; arr[j] &gt; temp; j-=gap) &#123;</div><div class="line">　　　　　　　　arr[j+gap] = arr[j];</div><div class="line">　　　　　　&#125;</div><div class="line">　　　　　　arr[j+gap] = temp;</div><div class="line">　　　　&#125;</div><div class="line">　　&#125;</div><div class="line">　　<span class="keyword">return</span> arr;</div><div class="line">&#125;</div><div class="line"><span class="keyword">var</span> arr=[<span class="number">3</span>,<span class="number">44</span>,<span class="number">38</span>,<span class="number">5</span>,<span class="number">47</span>,<span class="number">15</span>,<span class="number">36</span>,<span class="number">26</span>,<span class="number">27</span>,<span class="number">2</span>,<span class="number">46</span>,<span class="number">4</span>,<span class="number">19</span>,<span class="number">50</span>,<span class="number">48</span>];</div><div class="line"><span class="built_in">console</span>.log(shellSort(arr));</div></pre></td></tr></table></figure></p>
<h3 id="5、归并排序"><a href="#5、归并排序" class="headerlink" title="5、归并排序"></a>5、归并排序</h3><p>将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">function</span> <span class="title">mergeSort</span>(<span class="params">arr</span>) </span>&#123; <span class="comment">//采用自上而下的递归方法</span></div><div class="line">　　<span class="keyword">var</span> len = arr.length;</div><div class="line">　　<span class="keyword">if</span>(len &lt; <span class="number">2</span>) &#123;</div><div class="line">　　　　<span class="keyword">return</span> arr;</div><div class="line">　　&#125;</div><div class="line">　　<span class="keyword">var</span> middle = <span class="built_in">Math</span>.floor(len / <span class="number">2</span>),</div><div class="line">　　left = arr.slice(<span class="number">0</span>, middle),</div><div class="line">　　right = arr.slice(middle);</div><div class="line">　　<span class="keyword">return</span> merge(mergeSort(left), mergeSort(right));</div><div class="line">&#125;</div><div class="line"> </div><div class="line"><span class="function"><span class="keyword">function</span> <span class="title">merge</span>(<span class="params">left, right</span>)</span>&#123;</div><div class="line">　　<span class="keyword">var</span> result = [];</div><div class="line">　　<span class="keyword">while</span> (left.length &amp;&amp; right.length) &#123;</div><div class="line">　　　　<span class="keyword">if</span> (left[<span class="number">0</span>] &lt;= right[<span class="number">0</span>]) &#123;</div><div class="line">　　　　　　result.push(left.shift());</div><div class="line">　　　　&#125; <span class="keyword">else</span> &#123;</div><div class="line">　　　　　　result.push(right.shift());</div><div class="line">　　　　&#125;</div><div class="line">　　&#125;</div><div class="line"> </div><div class="line">　　<span class="keyword">while</span> (left.length)&#123;</div><div class="line">　　　　result.push(left.shift());</div><div class="line">　　&#125;</div><div class="line">　　<span class="keyword">while</span> (right.length)&#123;</div><div class="line">　　　　result.push(right.shift());</div><div class="line">　　&#125;</div><div class="line">　　<span class="keyword">return</span> result;</div><div class="line">&#125;</div><div class="line"><span class="keyword">var</span> arr=[<span class="number">3</span>,<span class="number">44</span>,<span class="number">38</span>,<span class="number">5</span>,<span class="number">47</span>,<span class="number">15</span>,<span class="number">36</span>,<span class="number">26</span>,<span class="number">27</span>,<span class="number">2</span>,<span class="number">46</span>,<span class="number">4</span>,<span class="number">19</span>,<span class="number">50</span>,<span class="number">48</span>];</div><div class="line"><span class="built_in">console</span>.log(mergeSort(arr));</div></pre></td></tr></table></figure></p>
<h3 id="6、快速排序"><a href="#6、快速排序" class="headerlink" title="6、快速排序"></a>6、快速排序</h3><p>通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,<br>以此达到整个数据变成有序序列<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">function</span> <span class="title">quickSort</span>(<span class="params">array, left, right</span>) </span>&#123;</div><div class="line">　　<span class="keyword">if</span> (left &lt; right) &#123;</div><div class="line">　　　　<span class="keyword">var</span> x = array[right], i = left - <span class="number">1</span>, temp;</div><div class="line">　　　　<span class="keyword">for</span> (<span class="keyword">var</span> j = left; j &lt;= right; j++) &#123;</div><div class="line">　　　　　　<span class="keyword">if</span> (array[j] &lt;= x) &#123;</div><div class="line">　　　　　　　　i++;</div><div class="line">　　　　　　　　temp = array[i];</div><div class="line">　　　　　　　　array[i] = array[j];</div><div class="line">　　　　　　　　array[j] = temp;</div><div class="line">　　　　　　&#125;</div><div class="line">　　　　&#125;</div><div class="line">　　　　<span class="built_in">console</span>.log(array) ;</div><div class="line">　　　　<span class="built_in">console</span>.log(left,i) ;</div><div class="line">　　　　quickSort(array, left, i - <span class="number">1</span>);</div><div class="line">　　　　<span class="built_in">console</span>.log(array)</div><div class="line">　　　　<span class="built_in">console</span>.log(i,right)</div><div class="line">　　　　quickSort(array, i + <span class="number">1</span>, right);</div><div class="line">　　&#125;</div><div class="line">　　<span class="built_in">console</span>.log(array)</div><div class="line">　　<span class="keyword">return</span> array;</div><div class="line">&#125;</div><div class="line"><span class="keyword">var</span> arr=[<span class="number">3</span>,<span class="number">44</span>,<span class="number">38</span>,<span class="number">5</span>,<span class="number">47</span>,<span class="number">15</span>,<span class="number">36</span>,<span class="number">26</span>,<span class="number">27</span>,<span class="number">2</span>,<span class="number">46</span>,<span class="number">4</span>,<span class="number">19</span>,<span class="number">50</span>,<span class="number">48</span>];</div><div class="line"><span class="built_in">console</span>.log(quickSort(arr,<span class="number">0</span>,arr.length<span class="number">-1</span>));</div></pre></td></tr></table></figure></p>
<h3 id="7、堆排序"><a href="#7、堆排序" class="headerlink" title="7、堆排序"></a>7、堆排序</h3><p>Heapsort是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">function</span> <span class="title">heapSort</span>(<span class="params">array</span>) </span>&#123;</div><div class="line">　　<span class="keyword">var</span> heapSize = array.length, temp;</div><div class="line">　　<span class="keyword">for</span> (<span class="keyword">var</span> i = <span class="built_in">Math</span>.floor(heapSize / <span class="number">2</span>) - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i--) &#123;　　</div><div class="line">　　　　heapify(array, i, heapSize);</div><div class="line">　　&#125;</div><div class="line">　　<span class="comment">//堆排序</span></div><div class="line">　　<span class="keyword">for</span> (<span class="keyword">var</span> j = heapSize - <span class="number">1</span>; j &gt;= <span class="number">1</span>; j--) &#123;</div><div class="line">　　　　temp = array[<span class="number">0</span>];</div><div class="line">　　　　array[<span class="number">0</span>] = array[j];</div><div class="line">　　　　array[j] = temp;</div><div class="line">　　　　<span class="built_in">console</span>.log(array)</div><div class="line">　　　　heapify(array, <span class="number">0</span>, --heapSize);</div><div class="line">　　&#125;</div><div class="line">　　<span class="keyword">return</span> array;</div><div class="line">&#125;</div><div class="line"><span class="function"><span class="keyword">function</span> <span class="title">heapify</span>(<span class="params">arr, x, len</span>) </span>&#123;</div><div class="line">　　<span class="keyword">var</span> l = <span class="number">2</span> * x + <span class="number">1</span>, r = <span class="number">2</span> * x + <span class="number">2</span>, largest = x, temp;</div><div class="line">　　<span class="keyword">if</span> (l &lt; len &amp;&amp; arr[l] &gt; arr[largest]) &#123;</div><div class="line">　　　　largest = l;</div><div class="line">　　&#125;</div><div class="line">　　<span class="keyword">if</span> (r &lt; len &amp;&amp; arr[r] &gt; arr[largest]) &#123;</div><div class="line">　　　　largest = r;</div><div class="line">　　&#125;</div><div class="line">　　<span class="keyword">if</span> (largest != x) &#123;</div><div class="line">　　　　temp = arr[x];</div><div class="line">　　　　arr[x] = arr[largest];</div><div class="line">　　　　arr[largest] = temp;</div><div class="line">　　　　<span class="built_in">console</span>.log(arr)</div><div class="line">　　　　heapify(arr, largest, len);</div><div class="line">　　&#125;</div><div class="line">&#125;</div><div class="line"><span class="keyword">var</span> arr=[<span class="number">91</span>,<span class="number">60</span>,<span class="number">96</span>,<span class="number">13</span>,<span class="number">35</span>,<span class="number">65</span>,<span class="number">46</span>,<span class="number">65</span>,<span class="number">10</span>,<span class="number">30</span>,<span class="number">20</span>,<span class="number">31</span>,<span class="number">77</span>,<span class="number">81</span>,<span class="number">22</span>];</div><div class="line"><span class="built_in">console</span>.log(heapSort(arr));</div></pre></td></tr></table></figure></p>
<h3 id="8、计数排序"><a href="#8、计数排序" class="headerlink" title="8、计数排序"></a>8、计数排序</h3><p>对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直<br>接存放到最终的输出序列的正确位置上。<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">function</span> <span class="title">countingSort</span>(<span class="params">array</span>) </span>&#123;</div><div class="line">　　<span class="keyword">var</span> len = array.length,</div><div class="line">　　B = [],</div><div class="line">　　C = [],</div><div class="line">　　min = max = array[<span class="number">0</span>];</div><div class="line">　　<span class="keyword">for</span> (<span class="keyword">var</span> i = <span class="number">0</span>; i &lt; len; i++) &#123;</div><div class="line">　　　　min = min &lt;= array[i] ? min : array[i];</div><div class="line">　　　　max = max &gt;= array[i] ? max : array[i];</div><div class="line">　　　　C[array[i]] = C[array[i]] ? C[array[i]] + <span class="number">1</span> : <span class="number">1</span>;</div><div class="line">　　　　<span class="built_in">console</span>.log(C)</div><div class="line">　　&#125;</div><div class="line">　　<span class="keyword">for</span> (<span class="keyword">var</span> j = min; j &lt; max; j++) &#123;</div><div class="line">　　　　C[j + <span class="number">1</span>] = (C[j + <span class="number">1</span>] || <span class="number">0</span>) + (C[j] || <span class="number">0</span>);</div><div class="line">　　　　<span class="built_in">console</span>.log(C)</div><div class="line">　　&#125;</div><div class="line">　　<span class="keyword">for</span> (<span class="keyword">var</span> k = len - <span class="number">1</span>; k &gt;= <span class="number">0</span>; k--) &#123;</div><div class="line">　　　　B[C[array[k]] - <span class="number">1</span>] = array[k];</div><div class="line">　　　　C[array[k]]--;</div><div class="line">　　　　<span class="built_in">console</span>.log(B)</div><div class="line">　　&#125;</div><div class="line">　　<span class="keyword">return</span> B;</div><div class="line">&#125;</div><div class="line"><span class="keyword">var</span> arr = [<span class="number">2</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">8</span>, <span class="number">7</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">2</span>, <span class="number">2</span>, <span class="number">7</span>, <span class="number">3</span>, <span class="number">9</span>, <span class="number">8</span>, <span class="number">2</span>, <span class="number">1</span>, <span class="number">4</span>, <span class="number">2</span>, <span class="number">4</span>, <span class="number">6</span>, <span class="number">9</span>, <span class="number">2</span>];</div><div class="line"><span class="built_in">console</span>.log(countingSort(arr));</div></pre></td></tr></table></figure></p>
<h3 id="9、桶排序"><a href="#9、桶排序" class="headerlink" title="9、桶排序"></a>9、桶排序</h3><p>将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">function</span> <span class="title">bucketSort</span>(<span class="params">array, num</span>) </span>&#123;</div><div class="line">　　<span class="keyword">if</span> (array.length &lt;= <span class="number">1</span>) &#123;</div><div class="line">　　　　<span class="keyword">return</span> array;</div><div class="line">　　&#125;</div><div class="line">　　<span class="keyword">var</span> len = array.length, buckets = [], result = [], min = max = array[<span class="number">0</span>], space, n = <span class="number">0</span>;</div><div class="line"></div><div class="line">　　<span class="keyword">var</span> index = <span class="built_in">Math</span>.floor(len / num) ;</div><div class="line">　　<span class="keyword">while</span>(index&lt;<span class="number">2</span>)&#123;</div><div class="line"></div><div class="line">　　　　num--;</div><div class="line">　　　　index = <span class="built_in">Math</span>.floor(len / num) ;</div><div class="line">　　&#125;</div><div class="line"></div><div class="line">　　<span class="keyword">for</span> (<span class="keyword">var</span> i = <span class="number">1</span>; i &lt; len; i++) &#123;</div><div class="line">　　　　min = min &lt;= array[i] ? min : array[i];</div><div class="line">　　　　max = max &gt;= array[i] ? max : array[i];</div><div class="line">　　&#125;</div><div class="line">　　space = (max - min + <span class="number">1</span>) / num;  <span class="comment">//步长</span></div><div class="line">　　<span class="keyword">for</span> (<span class="keyword">var</span> j = <span class="number">0</span>; j &lt; len; j++) &#123;</div><div class="line">　　　　<span class="keyword">var</span> index = <span class="built_in">Math</span>.floor((array[j] - min) / space);</div><div class="line">　　　　<span class="keyword">if</span> (buckets[index]) &#123; <span class="comment">// 非空桶，插入排序</span></div><div class="line">　　　　　　<span class="keyword">var</span> k = buckets[index].length - <span class="number">1</span>;</div><div class="line">　　　　　　<span class="keyword">while</span> (k &gt;= <span class="number">0</span> &amp;&amp; buckets[index][k] &gt; array[j]) &#123;</div><div class="line">　　　　　　　　buckets[index][k + <span class="number">1</span>] = buckets[index][k];</div><div class="line">　　　　　　　　k--;</div><div class="line">　　　　　　&#125;</div><div class="line">　　　　　　buckets[index][k + <span class="number">1</span>] = array[j];</div><div class="line">　　　　&#125; <span class="keyword">else</span> &#123; <span class="comment">//空桶，初始化</span></div><div class="line">　　　　　　buckets[index] = [];</div><div class="line">　　　　　　buckets[index].push(array[j]);</div><div class="line">　　　　&#125;</div><div class="line">　　&#125;</div><div class="line">　　<span class="keyword">while</span> (n &lt; num) &#123;</div><div class="line">　　　　result = result.concat(buckets[n]);</div><div class="line">　　　　n++;</div><div class="line">　　&#125;</div><div class="line">　　<span class="keyword">return</span> result;</div><div class="line">&#125;</div><div class="line"><span class="keyword">var</span> arr=[<span class="number">3</span>,<span class="number">44</span>,<span class="number">38</span>,<span class="number">5</span>,<span class="number">47</span>,<span class="number">15</span>,<span class="number">36</span>,<span class="number">26</span>,<span class="number">27</span>,<span class="number">2</span>,<span class="number">46</span>,<span class="number">4</span>,<span class="number">19</span>,<span class="number">50</span>,<span class="number">48</span>];</div><div class="line"><span class="built_in">console</span>.log(bucketSort(arr,<span class="number">4</span>));</div></pre></td></tr></table></figure></p>
<h3 id="10、基数排序"><a href="#10、基数排序" class="headerlink" title="10、基数排序"></a>10、基数排序</h3><p>透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)<br>，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">function</span> <span class="title">radixSort</span>(<span class="params">arr, maxDigit</span>) </span>&#123;</div><div class="line">　　<span class="keyword">var</span> mod = <span class="number">10</span>;</div><div class="line">　　<span class="keyword">var</span> dev = <span class="number">1</span>;</div><div class="line">　　<span class="keyword">var</span> counter = [];</div><div class="line">　　<span class="keyword">for</span> (<span class="keyword">var</span> i = <span class="number">0</span>; i &lt; maxDigit; i++, dev *= <span class="number">10</span>, mod *= <span class="number">10</span>) &#123;</div><div class="line">　　　　<span class="keyword">for</span>(<span class="keyword">var</span> j = <span class="number">0</span>; j &lt; arr.length; j++) &#123;</div><div class="line">　　　　　　<span class="keyword">var</span> bucket = <span class="built_in">parseInt</span>((arr[j] % mod) / dev);</div><div class="line">　　　　　　<span class="keyword">if</span>(counter[bucket]== <span class="literal">null</span>) &#123;</div><div class="line">　　　　　　　　counter[bucket] = [];</div><div class="line">　　　　　　&#125;</div><div class="line">　　　　counter[bucket].push(arr[j]);</div><div class="line">　　　　&#125;</div><div class="line">　　　　<span class="keyword">var</span> pos = <span class="number">0</span>;</div><div class="line">　　　　<span class="keyword">for</span>(<span class="keyword">var</span> j = <span class="number">0</span>; j &lt; counter.length; j++) &#123;</div><div class="line">　　　　　　<span class="keyword">var</span> value = <span class="literal">null</span>;</div><div class="line">　　　　　　<span class="keyword">if</span>(counter[j]!=<span class="literal">null</span>) &#123;</div><div class="line">　　　　　　　　<span class="keyword">while</span> ((value = counter[j].shift()) != <span class="literal">null</span>) &#123;</div><div class="line">　　　　　　　　　　arr[pos++] = value;</div><div class="line">　　　　　　　　&#125;</div><div class="line">　　　　　　&#125;</div><div class="line">　　　　&#125;</div><div class="line">　　&#125;</div><div class="line">　　<span class="keyword">return</span> arr;</div><div class="line">&#125;</div><div class="line"><span class="keyword">var</span> arr = [<span class="number">3</span>, <span class="number">44</span>, <span class="number">38</span>, <span class="number">5</span>, <span class="number">47</span>, <span class="number">15</span>, <span class="number">36</span>, <span class="number">26</span>, <span class="number">27</span>, <span class="number">2</span>, <span class="number">46</span>, <span class="number">4</span>, <span class="number">19</span>, <span class="number">50</span>, <span class="number">48</span>];</div><div class="line"><span class="built_in">console</span>.log(radixSort(arr,<span class="number">2</span>));</div></pre></td></tr></table></figure></p>

        </div>

        <blockquote class="post-copyright">
    <div class="content">
        
<span class="post-time">
    最后更新时间：<time datetime="2020-01-13T15:37:33.065Z" itemprop="dateUpdated">2020-01-13 23:37:33</time>
</span><br>


        
        谢谢浏览，我会继续努力的，示例：<a href="/2018/12/20/数据结构与算法之美手记/" target="_blank" rel="external">http://yoursite.com/2018/12/20/数据结构与算法之美手记/</a>
        
    </div>
    <footer>
        <a href="http://yoursite.com">
            <img src="/img/avatar.jpg" alt="BingZhenhuang">
            BingZhenhuang
        </a>
    </footer>
</blockquote>

        
<div class="page-reward">
    <a id="rewardBtn" href="javascript:;" class="page-reward-btn waves-effect waves-circle waves-light">赏</a>
</div>



        <div class="post-footer">
            
	<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/算法/">算法</a></li></ul>


            
<div class="page-share-wrap">
    

<div class="page-share" id="pageShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=http://yoursite.com/2018/12/20/数据结构与算法之美手记/&title=《数据结构与算法之美手记》 — 小方块 - hhardyy.com&pic=http://yoursite.com/img/avatar.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=http://yoursite.com/2018/12/20/数据结构与算法之美手记/&title=《数据结构与算法之美手记》 — 小方块 - hhardyy.com&source=跟随Google大佬的脚步。。。（一如既往的跟不上）
" data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=http://yoursite.com/2018/12/20/数据结构与算法之美手记/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《数据结构与算法之美手记》 — 小方块 - hhardyy.com&url=http://yoursite.com/2018/12/20/数据结构与算法之美手记/&via=http://yoursite.com" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=http://yoursite.com/2018/12/20/数据结构与算法之美手记/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>



    <a href="javascript:;" id="shareFab" class="page-share-fab waves-effect waves-circle">
        <i class="icon icon-share-alt icon-lg"></i>
    </a>
</div>



        </div>
    </div>

    
<nav class="post-nav flex-row flex-justify-between">
  
    <div class="waves-block waves-effect prev">
      <a href="/2019/01/20/React-echars做的图表组件/" id="post-prev" class="post-nav-link">
        <div class="tips"><i class="icon icon-angle-left icon-lg icon-pr"></i> Prev</div>
        <h4 class="title">react+echars做的图表轮子</h4>
      </a>
    </div>
  

  
    <div class="waves-block waves-effect next">
      <a href="/2018/12/05/二叉树算法原理/" id="post-next" class="post-nav-link">
        <div class="tips">Next <i class="icon icon-angle-right icon-lg icon-pl"></i></div>
        <h4 class="title">二叉树算法原理</h4>
      </a>
    </div>
  
</nav>



    














</article>

<div id="reward" class="page-modal reward-lay">
    <a class="close" href="javascript:;"><i class="icon icon-close"></i></a>
    <h3 class="reward-title">
        <i class="icon icon-quote-left"></i>
        🤠 请我喝可乐！
        <i class="icon icon-quote-right"></i>
    </h3>
    <div class="reward-content" style="width:50%">
        
        <div class="reward-code" style="text-align:center">
            <div style="width:300px;margin:0px auto;">
               <img id="rewardCode" style="width:50%;height:60%;display:block; margin:0px auto;" src="/img/alipay.jpg" alt="支付宝打赏二维码">
               <span style="display:inline-block; margin-bottom:20px;">0.88(支付宝 aliPay)</span>
               <img id="rewardCode" style="width:50%;height:60%;display:block; margin:0px auto;" src="/img/wechat.jpg" alt="微信打赏二维码">
               <span style="display:inline-block;">0.88(微信 weChat)</span>
            </div>
        </div>
    </div>
</div>



</div>

        <script>
!function(e,t,a){function n(){c(".heart{width: 10px;height: 10px;position: fixed;background: #f00;transform: rotate(45deg);-webkit-transform: rotate(45deg);-moz-transform: rotate(45deg);}.heart:after,.heart:before{content: '';width: inherit;height: inherit;background: inherit;border-radius: 50%;-webkit-border-radius: 50%;-moz-border-radius: 50%;position: fixed;}.heart:after{top: -5px;}.heart:before{left: -5px;}"),o(),r()}function r(){for(var e=0;e<d.length;e++)d[e].alpha<=0?(t.body.removeChild(d[e].el),d.splice(e,1)):(d[e].y--,d[e].scale+=.004,d[e].alpha-=.013,d[e].el.style.cssText="left:"+d[e].x+"px;top:"+d[e].y+"px;opacity:"+d[e].alpha+";transform:scale("+d[e].scale+","+d[e].scale+") rotate(45deg);background:"+d[e].color+";z-index:99999");requestAnimationFrame(r)}function o(){var t="function"==typeof e.onclick&&e.onclick;e.onclick=function(e){t&&t(),i(e)}}function i(e){var a=t.createElement("div");a.className="heart",d.push({el:a,x:e.clientX-5,y:e.clientY-5,scale:1,alpha:1,color:s()}),t.body.appendChild(a)}function c(e){var a=t.createElement("style");a.type="text/css";try{a.appendChild(t.createTextNode(e))}catch(t){a.styleSheet.cssText=e}t.getElementsByTagName("head")[0].appendChild(a)}function s(){return"rgb("+~~(255*Math.random())+","+~~(255*Math.random())+","+~~(255*Math.random())+")"}var d=[];e.requestAnimationFrame=function(){return e.requestAnimationFrame||e.webkitRequestAnimationFrame||e.mozRequestAnimationFrame||e.oRequestAnimationFrame||e.msRequestAnimationFrame||function(e){setTimeout(e,1e3/60)}}(),n()}(window,document);
</script>
<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
<script>
    function secondToDate(second) {
        if (!second) {
            return 0;
        }
        var time = new Array(0, 0, 0, 0, 0);
        if (second >= 365 * 24 * 3600) {
            time[0] = parseInt(second / (365 * 24 * 3600));
            second %= 365 * 24 * 3600;
        }
        if (second >= 24 * 3600) {
            time[1] = parseInt(second / (24 * 3600));
            second %= 24 * 3600;
        }
        if (second >= 3600) {
            time[2] = parseInt(second / 3600);
            second %= 3600;
        }
        if (second >= 60) {
            time[3] = parseInt(second / 60);
            second %= 60;
        }
        if (second > 0) {
            time[4] = second;
        }
        return time;
    }</script>
<script type="text/javascript" language="javascript">
    function setTime() {
        var create_time = Math.round(new Date(Date.UTC(2017, 08, 18, 11, 42, 23)).getTime() / 1000);
        var timestamp = Math.round((new Date().getTime() + 8 * 60 * 60 * 1000) / 1000);
        currentTime = secondToDate((timestamp - create_time));
        currentTimeHtml = 'Running：' + currentTime[0] + '年 ' + currentTime[1] + '天 '
                + currentTime[2] + '时 ' + currentTime[3] + '分 ' + currentTime[4]
                + '秒';
        document.getElementById("htmer_time").innerHTML = currentTimeHtml;
    }    setInterval(setTime, 1000);
</script>
<footer class="footer">
    <div class="top">
        

        <p>
          <span id="busuanzi_container_page_pv">
             [&nbsp;浏览量：&nbsp;<span id="busuanzi_value_page_pv"></span>&nbsp;]
          </span>
        </p>
    </div>
    <div class="bottom">
        <p>
        <span>BingZhenhuang &copy; 2017 - 2020</span>
            <span>
                
                Power by <a href="https://hhardyy.github.io/" target="_blank">zhen On August 8</a> 
            </span>
            <span id="htmer_time" "></span>
        </p>
    </div>
</footer>

    </main>
    <div class="mask" id="mask"></div>
<a href="javascript:;" id="gotop" class="waves-effect waves-circle waves-light"><span class="icon icon-lg icon-chevron-up"></span></a>



<div class="global-share" id="globalShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=http://yoursite.com/2018/12/20/数据结构与算法之美手记/&title=《数据结构与算法之美手记》 — 小方块 - hhardyy.com&pic=http://yoursite.com/img/avatar.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=http://yoursite.com/2018/12/20/数据结构与算法之美手记/&title=《数据结构与算法之美手记》 — 小方块 - hhardyy.com&source=跟随Google大佬的脚步。。。（一如既往的跟不上）
" data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=http://yoursite.com/2018/12/20/数据结构与算法之美手记/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《数据结构与算法之美手记》 — 小方块 - hhardyy.com&url=http://yoursite.com/2018/12/20/数据结构与算法之美手记/&via=http://yoursite.com" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=http://yoursite.com/2018/12/20/数据结构与算法之美手记/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>


<div class="page-modal wx-share" id="wxShare">
    <a class="close" href="javascript:;"><i class="icon icon-close"></i></a>
    <p>扫一扫，分享到微信</p>
    <img src="" alt="微信分享二维码">
</div>




    <script src="//cdn.bootcss.com/node-waves/0.7.4/waves.min.js"></script>
<script>
var BLOG = { ROOT: '/', SHARE: true, REWARD: true };


</script>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/main.min.js"></script>


<div class="search-panel" id="search-panel">
    <ul class="search-result" id="search-result"></ul>
</div>
<template id="search-tpl">
<li class="item">
    <a href="{path}" class="waves-block waves-effect">
        <div class="title ellipsis" title="{title}">{title}</div>
        <div class="flex-row flex-middle">
            <div class="tags ellipsis">
                {tags}
            </div>
            <time class="flex-col time">{date}</time>
        </div>
    </a>
</li>
</template>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/search.min.js" async></script>








<script>
(function() {
    var OriginTitile = document.title, titleTime;
    document.addEventListener('visibilitychange', function() {
        if (document.hidden) {
            document.title = '(•‾̑⌣‾̑•)✧˖°回来看我';
            clearTimeout(titleTime);
        } else {
            document.title = '(゜-゜)つロ欢迎回来';
            titleTime = setTimeout(function() {
                document.title = OriginTitile;
            },2000);
        }
    });
})();
</script>



</body>
</html>
